package practise.alogrithm.introductionToAlogrithm.SortingAndOrderStatistics;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by Richard on 7/19/2014.
 */
public class QuickSort {
    public static List<Integer> quickSort(List<Integer> values, int start, int end){
        if(start>=end){
            return values;
        }
        int recordEnd = end;
        int index = start;
        while(end-index>=1){
            if(values.get(index)==values.get(index+1)){
                index++;
            }
            else if(values.get(index)>values.get(index+1)){
                int temp = values.get(index);
                values.set(index,values.get(index+1));
                values.set(index+1,temp);
                index++;
            }
            else if(values.get(index)<values.get(index+1)){
                int temp = values.get(end);
                values.set(end,values.get(index+1));// notice there, we check the next one every time
                values.set(index+1,temp);
                end--;
            }
        }

        quickSort(values,start,index);//we cannot decrease the number there as end=index-1, as when the min number at first, then it will dead loop
        quickSort(values,index+1,recordEnd);

        return values;
    }



    public static void main(String[] args){
        List<Integer> array = new ArrayList<>(Arrays.asList(new Integer[]{1, 3, 2, 5, 4, 6, 7, 8, 0, 9,}));
        for(Integer value: quickSort(array,0,array.size()-1))
            System.out.print("["+value+"]");
    }
}
